Back to course home
0% completed
Vote For New Content
Burst Balloons (hard)
Problem Statement
You are given a row of n balloons, each marked with a specific number i.e. ith ballon is marked with nums[i], wheres nums is an integer array. You are asked to burst all the balloons.
When you burst the ith balloon, you get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 indexes are
out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
Return the highest possible coin total after popping all the balloons.
Examples
-
Example 1:
- Input:
[3, 1, 5] - Expected Output:
35 - Justification: Popping balloon 1 (value 1) first earns
3*1*5=15coins, leaving[3, 5].Next, pop3to earn1*3*5=15, and finally pop5to earn1*5*1=5, for a total of15+15+5=35coins.
- Input:
-
Example 2:
- Input:
[1, 5, 8] - Expected Output:
56 - Justification: First, pop balloon 1 (value 5), earning
1*5*8=40coins, leaving[1, 8]. Then, pop balloons 0 and 2, earning1*1*8=8and1*8*1=8coins respectively, for a total of40+8+8=56coins.
- Input:
-
Example 3:
- Input:
[2, 4, 3, 5] - Expected Output:
115 - Justification: A strategic approach yields the maximum coins: start with balloon 2 (value 3) for
4*3*5=60, then balloon 2 (value 4) for2*4*5=40, followed by the outer balloons,1*2*5=10and1*5*1=5, summing up to24+30+10+2=115coins.
- Input:
Try it yourself
Try solving this question here:
Java
Saved to Cloud
. . . .
Solution: Arithmetic Slices II - Subsequence
Solution: Burst Balloons
Mark as Completed
On this page
Problem Statement
Examples
Try it yourself